All LeetCode problems with likes and dislikes

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

• -231 <= x <= 231 - 1

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
6. Return the integer as the final result.

Note:

• Only the space character ' ' is considered a whitespace character.
• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.

Example 2:

Input: s = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
Step 3: "   -42" ("42" is read in)
               ^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.

Example 3:

Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
             ^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

Constraints:

• 0 <= s.length <= 200
• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

• -231 <= x <= 231 - 1

class Solution {
public:
    bool isPalindrome(long long int x) {
        if(x<0)
            return false;
        long long int n=0,n1=x;
        while(x)
        {
            n=n*10+x%10;
            x/=10;
        }
        // cout<
  

class Solution {
public:
    bool isPalindrome(long long int x) {
        if(x<0)
            return false;
        long long int n=0,n1=x;
        while(x)
        {
            n=n*10+x%10;
            x/=10;
        }
        // cout<

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= num <= 3999

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

class Solution {
public:
    string longestCommonPrefix(vector& strs) 
    {
        if(strs.size()==0)
            return "";
        int fre[26]={0},i=0;
        string ans="";
        while(i
  

class Solution {
public:
    string longestCommonPrefix(vector& strs) 
    {
        if(strs.size()==0)
            return "";
        int fre[26]={0},i=0;
        string ans="";
        while(i

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

class Solution {
public:
    string nums[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector ans;
    
    void find(string s,string cur,int cur_i)
    {
        if(cur.size()==s.size())
        {
            ans.push_back(cur);    
            return;
        }
        
        for(auto ch : nums[s[cur_i]-'0'])
            find(s,cur+ch,cur_i+1);
    }
    
    vector letterCombinations(string digits) {
        
        ans.clear();
        
        if(digits.length())
            find(digits,"",0);
        
        return ans;
    }
};

class Solution {
public:
    string nums[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector ans;
    
    void find(string s,string cur,int cur_i)
    {
        if(cur.size()==s.size())
        {
            ans.push_back(cur);    
            return;
        }
        
        for(auto ch : nums[s[cur_i]-'0'])
            find(s,cur+ch,cur_i+1);
    }
    
    vector letterCombinations(string digits) {
        
        ans.clear();
        
        if(digits.length())
            find(digits,"",0);
        
        return ans;
    }
};

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        int i,j,left,right,n=nums.size();
        sort(nums.begin(),nums.end());
        vector> ans;
        for(i=0;irem)
                        right--;
                    else
                    {
                        ans.push_back({nums[i],nums[j],nums[left],nums[right]});
                        while(left
  

class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        int i,j,left,right,n=nums.size();
        sort(nums.begin(),nums.end());
        vector> ans;
        for(i=0;irem)
                        right--;
                    else
                    {
                        ans.push_back({nums[i],nums[j],nums[left],nums[right]});
                        while(left

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

class Solution {
public:
    bool isValid(string s) {
        stack st;
        int i;
        for(i=0;i0 && s[i]==')' && st.top()=='(')
                st.pop();
            else if(st.size()>0 && s[i]==']' && st.top()=='[')
                st.pop();
            else if(st.size()>0 && s[i]=='}' && st.top()=='{')
                st.pop();
            else
                st.push(s[i]);
        }
        if(st.size())
            return false;
        return true;
    }
};

class Solution {
public:
    bool isValid(string s) {
        stack st;
        int i;
        for(i=0;i0 && s[i]==')' && st.top()=='(')
                st.pop();
            else if(st.size()>0 && s[i]==']' && st.top()=='[')
                st.pop();
            else if(st.size()>0 && s[i]=='}' && st.top()=='{')
                st.pop();
            else
                st.push(s[i]);
        }
        if(st.size())
            return false;
        return true;
    }
};

class Solution {
public:
    bool isValid(string s) {
        stack st;
        int i;
        for(i=0;i0 && s[i]==')' && st.top()=='(')
                st.pop();
            else if(st.size()>0 && s[i]==']' && st.top()=='[')
                st.pop();
            else if(st.size()>0 && s[i]=='}' && st.top()=='{')
                st.pop();
            else
                st.push(s[i]);
        }
        if(st.size())
            return false;
        return true;
    }
};

class Solution {
public:
    bool isValid(string s) {
        stack st;
        int i;
        for(i=0;i0 && s[i]==')' && st.top()=='(')
                st.pop();
            else if(st.size()>0 && s[i]==']' && st.top()=='[')
                st.pop();
            else if(st.size()>0 && s[i]=='}' && st.top()=='{')
                st.pop();
            else
                st.push(s[i]);
        }
        if(st.size())
            return false;
        return true;
    }
};

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)
            return NULL;
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        
        ListNode *cur_node,*head;
        int f=0;
        while(l1!=NULL || l2!=NULL)
        {
            if(f==0)
            {
                if(l1->valval)
                {
                    head=l1;
                    l1=l1->next;
                }
                else
                {
                    head=l2;
                    l2=l2->next;
                }
                cur_node=head;
                f=1;
                continue;
            }
            
            if(l1!=NULL && l2!=NULL)
            {
                if(l1->valval)
                {
                    cur_node->next=l1;
                    l1=l1->next;
                }
                else
                {
                    cur_node->next=l2;
                    l2=l2->next;
                }
            }
            else if(l1==NULL && l2!=NULL)
            {
                cur_node->next=l2;
                l2=l2->next;
            }
            else if(l1!=NULL && l2==NULL)
            {
                cur_node->next=l1;
                l1=l1->next;
            }
            cur_node=cur_node->next;
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)
            return NULL;
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        
        ListNode *cur_node,*head;
        int f=0;
        while(l1!=NULL || l2!=NULL)
        {
            if(f==0)
            {
                if(l1->valval)
                {
                    head=l1;
                    l1=l1->next;
                }
                else
                {
                    head=l2;
                    l2=l2->next;
                }
                cur_node=head;
                f=1;
                continue;
            }
            
            if(l1!=NULL && l2!=NULL)
            {
                if(l1->valval)
                {
                    cur_node->next=l1;
                    l1=l1->next;
                }
                else
                {
                    cur_node->next=l2;
                    l2=l2->next;
                }
            }
            else if(l1==NULL && l2!=NULL)
            {
                cur_node->next=l2;
                l2=l2->next;
            }
            else if(l1!=NULL && l2==NULL)
            {
                cur_node->next=l1;
                l1=l1->next;
            }
            cur_node=cur_node->next;
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)
            return NULL;
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        
        ListNode *cur_node,*head;
        int f=0;
        while(l1!=NULL || l2!=NULL)
        {
            if(f==0)
            {
                if(l1->valval)
                {
                    head=l1;
                    l1=l1->next;
                }
                else
                {
                    head=l2;
                    l2=l2->next;
                }
                cur_node=head;
                // cur_node->next=NULL;
                f=1;
                continue;
            }
            
            if(l1!=NULL && l2!=NULL)
            {
                if(l1->valval)
                {
                    cur_node->next=l1;
                    l1=l1->next;
                }
                else
                {
                    cur_node->next=l2;
                    l2=l2->next;
                }
                cur_node=cur_node->next;
                // cur_node->next=NULL;
            }
            else if(l1==NULL && l2!=NULL)
            {
                cur_node->next=l2;
                l2=l2->next;
                cur_node=cur_node->next;
                // cur_node->next=NULL;
            }
            else if(l1!=NULL && l2==NULL)
            {
                cur_node->next=l1;
                l1=l1->next;
                cur_node=cur_node->next;
                // cur_node->next=NULL;
            }
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)
            return NULL;
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        
        ListNode *cur_node,*head;
        int f=0;
        while(l1!=NULL || l2!=NULL)
        {
            if(f==0)
            {
                if(l1->valval)
                {
                    head=l1;
                    l1=l1->next;
                }
                else
                {
                    head=l2;
                    l2=l2->next;
                }
                cur_node=head;
                // cur_node->next=NULL;
                f=1;
                continue;
            }
            
            if(l1!=NULL && l2!=NULL)
            {
                if(l1->valval)
                {
                    cur_node->next=l1;
                    l1=l1->next;
                }
                else
                {
                    cur_node->next=l2;
                    l2=l2->next;
                }
                cur_node=cur_node->next;
                // cur_node->next=NULL;
            }
            else if(l1==NULL && l2!=NULL)
            {
                cur_node->next=l2;
                l2=l2->next;
                cur_node=cur_node->next;
                // cur_node->next=NULL;
            }
            else if(l1!=NULL && l2==NULL)
            {
                cur_node->next=l1;
                l1=l1->next;
                cur_node=cur_node->next;
                // cur_node->next=NULL;
            }
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)
            return NULL;
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        
        ListNode *cur_node,*head;
        int f=0;
        while(l1!=NULL || l2!=NULL)
        {
            if(f==0)
            {
                if(l1->valval)
                {
                    head=l1;
                    l1=l1->next;
                }
                else
                {
                    head=l2;
                    l2=l2->next;
                }
                cur_node=head;
                cur_node->next=NULL;
                f=1;
                continue;
            }
            
            if(l1!=NULL && l2!=NULL)
            {
                if(l1->valval)
                {
                    cur_node->next=l1;
                    l1=l1->next;
                }
                else
                {
                    cur_node->next=l2;
                    l2=l2->next;
                }
                cur_node=cur_node->next;
                cur_node->next=NULL;
            }
            else if(l1==NULL && l2!=NULL)
            {
                cur_node->next=l2;
                l2=l2->next;
                cur_node=cur_node->next;
                cur_node->next=NULL;
            }
            else if(l1!=NULL && l2==NULL)
            {
                cur_node->next=l1;
                l1=l1->next;
                cur_node=cur_node->next;
                cur_node->next=NULL;
            }
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL && l2==NULL)
            return NULL;
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        
        ListNode *cur_node,*head;
        int f=0;
        while(l1!=NULL || l2!=NULL)
        {
            if(f==0)
            {
                if(l1->valval)
                {
                    head=l1;
                    l1=l1->next;
                }
                else
                {
                    head=l2;
                    l2=l2->next;
                }
                cur_node=head;
                cur_node->next=NULL;
                f=1;
                continue;
            }
            
            if(l1!=NULL && l2!=NULL)
            {
                if(l1->valval)
                {
                    cur_node->next=l1;
                    l1=l1->next;
                }
                else
                {
                    cur_node->next=l2;
                    l2=l2->next;
                }
                cur_node=cur_node->next;
                cur_node->next=NULL;
            }
            else if(l1==NULL && l2!=NULL)
            {
                cur_node->next=l2;
                l2=l2->next;
                cur_node=cur_node->next;
                cur_node->next=NULL;
            }
            else if(l1!=NULL && l2==NULL)
            {
                cur_node->next=l1;
                l1=l1->next;
                cur_node=cur_node->next;
                cur_node->next=NULL;
            }
        }
        return head;
    }
};

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        if(o==0 && c==0)
            ans.push_back(s);
        
        if(o<=c)
        {
            if(o>0)
                findAns(s+'(',o-1,c);
            if(c>0)
                findAns(s+')',o,c-1);
        }
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        if(o==0 && c==0)
            ans.push_back(s);
        
        if(o<=c)
        {
            if(o>0)
                findAns(s+'(',o-1,c);
            if(c>0)
                findAns(s+')',o,c-1);
        }
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        if(o==0 && c==0)
            ans.push_back(s);
        
        if(o<=c)
        {
            if(o>0)
                findAns(s+'(',o-1,c);
            if(c>0)
                findAns(s+')',o,c-1);
        }
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        if(o==0 && c==0)
            ans.push_back(s);
        
        if(o<=c)
        {
            if(o>0)
                findAns(s+'(',o-1,c);
            if(c>0)
                findAns(s+')',o,c-1);
        }
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        // cout< st;
//             for(auto ch : s)
//             {
//                 if(st.size()==0)
//                     st.push(ch);
//                 else
//                 {
//                     if(ch==')')
//                     {
//                         if(st.top()=='(')
//                             st.pop();
//                         else
//                             st.push(ch);
//                     }
//                     else
//                         st.push(ch);
//                 }
//             }
            
//             if(st.size()==0)
                ans.push_back(s);
        }
        
        if(o<=c)
        {
            if(o>0)
                findAns(s+'(',o-1,c);
            if(c>0)
                findAns(s+')',o,c-1);
        }
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        // cout< st;
//             for(auto ch : s)
//             {
//                 if(st.size()==0)
//                     st.push(ch);
//                 else
//                 {
//                     if(ch==')')
//                     {
//                         if(st.top()=='(')
//                             st.pop();
//                         else
//                             st.push(ch);
//                     }
//                     else
//                         st.push(ch);
//                 }
//             }
            
//             if(st.size()==0)
                ans.push_back(s);
        }
        
        if(o<=c)
        {
            if(o>0)
                findAns(s+'(',o-1,c);
            if(c>0)
                findAns(s+')',o,c-1);
        }
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        if(o==0 && c==0)
        {
            stack st;
            for(auto ch : s)
            {
                if(st.size()==0)
                    st.push(ch);
                else
                {
                    if(ch==')')
                    {
                        if(st.top()=='(')
                            st.pop();
                        else
                            st.push(ch);
                    }
                    else
                        st.push(ch);
                }
            }
            
            if(st.size()==0)
                ans.push_back(s);
            // return;
        }
        
        if(o>0)
            findAns(s+'(',o-1,c);
        if(c>0)
            findAns(s+')',o,c-1);
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

class Solution {
public:
    
    vector ans;
    
    void findAns(string s,int o,int c)
    {
        if(o==0 && c==0)
        {
            stack st;
            for(auto ch : s)
            {
                if(st.size()==0)
                    st.push(ch);
                else
                {
                    if(ch==')')
                    {
                        if(st.top()=='(')
                            st.pop();
                        else
                            st.push(ch);
                    }
                    else
                        st.push(ch);
                }
            }
            
            if(st.size()==0)
                ans.push_back(s);
            // return;
        }
        
        if(o>0)
            findAns(s+'(',o-1,c);
        if(c>0)
            findAns(s+')',o,c-1);
    }
    
    vector generateParenthesis(int n) {
        ans.clear();
        
        findAns("(",n-1,n);
        
        return ans;
    }
};

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int len=0;
        ListNode *p1=head,*p2;
        while(p1!=NULL)
        {
            len++;
            p1=p1->next;
        }
        int grps=len/k;
        p1=head,p2=head;
        while(grps--)
        {
            int temp=k;
            vector v;
            while(temp--)
            {
                v.push_back(p2->val);
                p2=p2->next;
            }
            // reverse(v.begin(),v.end());
            temp=k;
            int i=0;
            while(temp--)
            {
                p1->val=v[temp];
                p1=p1->next;
            }
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int len=0;
        ListNode *p1=head,*p2;
        while(p1!=NULL)
        {
            len++;
            p1=p1->next;
        }
        int grps=len/k;
        p1=head,p2=head;
        while(grps--)
        {
            int temp=k;
            vector v;
            while(temp--)
            {
                v.push_back(p2->val);
                p2=p2->next;
            }
            // reverse(v.begin(),v.end());
            temp=k;
            int i=0;
            while(temp--)
            {
                p1->val=v[temp];
                p1=p1->next;
            }
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int len=0;
        ListNode *p1=head,*p2;
        while(p1!=NULL)
        {
            len++;
            p1=p1->next;
        }
        int grps=len/k;
        p1=head,p2=head;
        while(grps--)
        {
            int temp=k;
            vector v;
            while(temp--)
            {
                v.push_back(p2->val);
                p2=p2->next;
            }
            reverse(v.begin(),v.end());
            for(auto el : v)
                    cout<next;
            temp=k;
            int i=0;
            while(temp--)
            {
                p1->val=v[i++];
                p1=p1->next;
            }
            // p1=p1->next;
        }
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int len=0;
        ListNode *p1=head,*p2;
        while(p1!=NULL)
        {
            len++;
            p1=p1->next;
        }
        int grps=len/k;
        p1=head,p2=head;
        while(grps--)
        {
            int temp=k;
            vector v;
            while(temp--)
            {
                v.push_back(p2->val);
                p2=p2->next;
            }
            reverse(v.begin(),v.end());
            for(auto el : v)
                    cout<next;
            temp=k;
            int i=0;
            while(temp--)
            {
                p1->val=v[i++];
                p1=p1->next;
            }
            // p1=p1->next;
        }
        return head;
    }
};

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

class Solution {
public:
    int strStr(string haystack, string needle) {
        int j=0,start=-1,i;
        int n=haystack.length(),m=needle.length();
        
        if(needle.size()>haystack.size())
            return -1;
        
        for(i=0;i<=n-needle.size();i++) {
            int possible=1;
            for(j=0;j
  

class Solution {
public:
    int strStr(string haystack, string needle) {
        int j=0,start=-1,i;
        int n=haystack.length(),m=needle.length();
        
        if(needle.size()>haystack.size())
            return -1;
        
        for(i=0;i<=n-needle.size();i++) {
            int possible=1;
            for(j=0;j

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.

Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 in s that is equal to the concatenation of any permutation of words.
We return an empty array.

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.

Constraints:

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• s and words[i] consist of lowercase English letters.

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

class Solution {
public:
    void nextPermutation(vector& nums) {
        if(nums.size()==0)
                return;
        int i,j;
        for(i=nums.size()-2;i>=0;i--)
            if(nums[i]=0)
        {
            for(j=nums.size()-1;j>=0;j--)
                if(nums[j]>nums[i])
                    break;
            swap(nums[i],nums[j]);
            i++,j=nums.size()-1;
            while(i
  

class Solution {
public:
    void nextPermutation(vector& nums) {
        if(nums.size()==0)
                return;
        int i,j;
        for(i=nums.size()-2;i>=0;i--)
            if(nums[i]=0)
        {
            for(j=nums.size()-1;j>=0;j--)
                if(nums[j]>nums[i])
                    break;
            swap(nums[i],nums[j]);
            i++,j=nums.size()-1;
            while(i

class Solution {
public:
    void nextPermutation(vector& nums) {
        bool b=next_permutation(nums.begin(),nums.end());
        for(auto el : nums)
                cout<
  

class Solution {
public:
    void nextPermutation(vector& nums) {
        bool b=next_permutation(nums.begin(),nums.end());
        for(auto el : nums)
                cout<

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

class Solution {
public:
    int ans[9][9];
    map> rowFreqMap;
    map> colFreqMap;
    map> boxFreqMap;
    int box[9][9];

    bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
        return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
    }

    bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
    map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
        if(cur==totalBlanks) {
            return true;
        }

        int curRow=blanks[cur].first;
        int curCol=blanks[cur].second;

        for(int i=1;i<=9;i++) {
            if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
                rowFreqMap[curRow][i]++;
                colFreqMap[curCol][i]++;
                boxFreqMap[box[curRow][curCol]][i]++;
                board[curRow][curCol]=char(i+'0');
                
                bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
                if(ansFound) {
                    return true;
                }
                
                rowFreqMap[curRow].erase(i);
                colFreqMap[curCol].erase(i);
                boxFreqMap[box[curRow][curCol]].erase(i);
                board[curRow][curCol]=0;
            }
        }
        return false;
    }

    void solveSudoku(vector>& board) {
        int i,j;
        vector> blanks;
       
        rowFreqMap.clear();
        colFreqMap.clear();
        boxFreqMap.clear();
        memset(ans,0,sizeof(ans));

        for(i=0;i<9;i++)
            for(j=0;j<9;j++) {
                if(board[i][j]!='.') {
                    rowFreqMap[i][board[i][j]-'0']++;
                    colFreqMap[j][board[i][j]-'0']++;
                    ans[i][j]=board[i][j]-'0';
                }
                if(board[i][j]=='.')
                    blanks.push_back({i,j});
            }
        
        int boxNo=1;
        for(i=0;i<9;i+=3) {
            for(j=0;j<9;j+=3) {
                for(int k=0;k<3;k++)
                    for(int l=0;l<3;l++) {
                        box[k+i][l+j]=boxNo;
                        if(board[k+i][l+j]!='.') 
                            boxFreqMap[boxNo][ans[k+i][l+j]]++;
                    }
                boxNo++;
            }
        }

        fillSudoku(board,blanks,0,blanks.size(),rowFreqMap,colFreqMap,boxFreqMap);
    }
};

class Solution {
public:
    int ans[9][9];
    map> rowFreqMap;
    map> colFreqMap;
    map> boxFreqMap;
    int box[9][9];

    bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
        return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
    }

    bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
    map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
        if(cur==totalBlanks) {
            return true;
        }

        int curRow=blanks[cur].first;
        int curCol=blanks[cur].second;

        for(int i=1;i<=9;i++) {
            if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
                rowFreqMap[curRow][i]++;
                colFreqMap[curCol][i]++;
                boxFreqMap[box[curRow][curCol]][i]++;
                board[curRow][curCol]=char(i+'0');
                
                bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
                if(ansFound) {
                    return true;
                }
                
                rowFreqMap[curRow].erase(i);
                colFreqMap[curCol].erase(i);
                boxFreqMap[box[curRow][curCol]].erase(i);
                board[curRow][curCol]=0;
            }
        }
        return false;
    }

    void solveSudoku(vector>& board) {
        int i,j;
        vector> blanks;
       
        rowFreqMap.clear();
        colFreqMap.clear();
        boxFreqMap.clear();
        memset(ans,0,sizeof(ans));

        for(i=0;i<9;i++)
            for(j=0;j<9;j++) {
                if(board[i][j]!='.') {
                    rowFreqMap[i][board[i][j]-'0']++;
                    colFreqMap[j][board[i][j]-'0']++;
                    ans[i][j]=board[i][j]-'0';
                }
                if(board[i][j]=='.')
                    blanks.push_back({i,j});
            }
        
        int boxNo=1;
        for(i=0;i<9;i+=3) {
            for(j=0;j<9;j+=3) {
                for(int k=0;k<3;k++)
                    for(int l=0;l<3;l++) {
                        box[k+i][l+j]=boxNo;
                        if(board[k+i][l+j]!='.') 
                            boxFreqMap[boxNo][ans[k+i][l+j]]++;
                    }
                boxNo++;
            }
        }

        fillSudoku(board,blanks,0,blanks.size(),rowFreqMap,colFreqMap,boxFreqMap);
    }
};

class Solution {
public:
    int ans[9][9];
    map> rowFreqMap;
    map> colFreqMap;
    map> boxFreqMap;
    int box[9][9];

    bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
        return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
    }

    bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
    map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
        if(cur==totalBlanks) {
            return true;
        }

        int curRow=blanks[cur].first;
        int curCol=blanks[cur].second;

        for(int i=1;i<=9;i++) {
            if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
                rowFreqMap[curRow][i]++;
                colFreqMap[curCol][i]++;
                boxFreqMap[box[curRow][curCol]][i]++;
                board[curRow][curCol]=char(i+'0');
                
                bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
                if(ansFound) {
                    return true;
                }
                
                rowFreqMap[curRow].erase(i);
                colFreqMap[curCol].erase(i);
                boxFreqMap[box[curRow][curCol]].erase(i);
                board[curRow][curCol]=0;
            }
        }
        return false;
    }

    void solveSudoku(vector>& board) {
        int i,j;
        vector> blanks;
       
        rowFreqMap.clear();
        colFreqMap.clear();
        boxFreqMap.clear();
        memset(ans,0,sizeof(ans));

        for(i=0;i<9;i++)
            for(j=0;j<9;j++) {
                if(board[i][j]!='.') {
                    rowFreqMap[i][board[i][j]-'0']++;
                    colFreqMap[j][board[i][j]-'0']++;
                    ans[i][j]=board[i][j]-'0';
                }
                if(board[i][j]=='.')
                    blanks.push_back({i,j});
            }

        // for(auto it: rowFreqMap) {
        //     cout<
  

class Solution {
public:
    int ans[9][9];
    map> rowFreqMap;
    map> colFreqMap;
    map> boxFreqMap;
    int box[9][9];

    bool validNumberToPut(int row,int col,int num,map> &rowFreqMap,map> &colFreqMap,map> &boxFreqMap) {
        return (rowFreqMap[row].find(num)==rowFreqMap[row].end() && colFreqMap[col].find(num)==colFreqMap[col].end() && boxFreqMap[box[row][col]].find(num)==boxFreqMap[box[row][col]].end());
    }

    bool fillSudoku(vector>& board,vector> blanks,int cur,int totalBlanks,
    map> &rowFreqMap, map> &colFreqMap,map> &boxFreqMap) {
        if(cur==totalBlanks) {
            return true;
        }

        int curRow=blanks[cur].first;
        int curCol=blanks[cur].second;

        for(int i=1;i<=9;i++) {
            if(validNumberToPut(curRow,curCol,i,rowFreqMap,colFreqMap,boxFreqMap)) {
                rowFreqMap[curRow][i]++;
                colFreqMap[curCol][i]++;
                boxFreqMap[box[curRow][curCol]][i]++;
                board[curRow][curCol]=char(i+'0');
                
                bool ansFound=fillSudoku(board,blanks,cur+1,totalBlanks,rowFreqMap,colFreqMap,boxFreqMap);
                if(ansFound) {
                    return true;
                }
                
                rowFreqMap[curRow].erase(i);
                colFreqMap[curCol].erase(i);
                boxFreqMap[box[curRow][curCol]].erase(i);
                board[curRow][curCol]=0;
            }
        }
        return false;
    }

    void solveSudoku(vector>& board) {
        int i,j;
        vector> blanks;
       
        rowFreqMap.clear();
        colFreqMap.clear();
        boxFreqMap.clear();
        memset(ans,0,sizeof(ans));

        for(i=0;i<9;i++)
            for(j=0;j<9;j++) {
                if(board[i][j]!='.') {
                    rowFreqMap[i][board[i][j]-'0']++;
                    colFreqMap[j][board[i][j]-'0']++;
                    ans[i][j]=board[i][j]-'0';
                }
                if(board[i][j]=='.')
                    blanks.push_back({i,j});
            }

        // for(auto it: rowFreqMap) {
        //     cout<

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

class Solution {
public:
    
    vector> ans;
    map,int> mp;
    
    void findAns(vector &a,int t,vector &cur,int index,int sum)
    {
        if(sum==t)
        {
            // sort(cur.begin(),cur.end());
            if(!mp[cur])
                ans.push_back(cur);
            mp[cur]++;
            return;
        }
            
        if(index>=a.size())
            return;
        
        
        if(sum+a[index]<=t)
        {
            vector temp=cur;
            temp.push_back(a[index]);
            findAns(a,t,temp,index+1,sum+a[index]);
            findAns(a,t,temp,index,sum+a[index]);
        }
        
        findAns(a,t,cur,index+1,sum);
    }
    
    vector> combinationSum(vector& a, int t) 
    {
        vector temp;
        findAns(a,t,temp,0,0);
        return ans;
    }
};

class Solution {
public:
    
    vector> ans;
    map,int> mp;
    
    void findAns(vector &a,int t,vector &cur,int index,int sum)
    {
        if(sum==t)
        {
            // sort(cur.begin(),cur.end());
            if(!mp[cur])
                ans.push_back(cur);
            mp[cur]++;
            return;
        }
            
        if(index>=a.size())
            return;
        
        
        if(sum+a[index]<=t)
        {
            vector temp=cur;
            temp.push_back(a[index]);
            findAns(a,t,temp,index+1,sum+a[index]);
            findAns(a,t,temp,index,sum+a[index]);
        }
        
        findAns(a,t,cur,index+1,sum);
    }
    
    vector> combinationSum(vector& a, int t) 
    {
        vector temp;
        findAns(a,t,temp,0,0);
        return ans;
    }
};

class Solution {
public:
    
    vector> ans;
    map,int> mp;
    
    void findAns(vector &a,int t,vector &cur,int index,int sum)
    {
        if(sum==t)
        {
            sort(cur.begin(),cur.end());
            if(!mp[cur])
                ans.push_back(cur);
            mp[cur]++;
            return;
        }
            
        if(index>=a.size())
            return;
        
        
        if(sum+a[index]<=t)
        {
            vector temp=cur;
            temp.push_back(a[index]);
            findAns(a,t,temp,index+1,sum+a[index]);
            findAns(a,t,temp,index,sum+a[index]);
        }
        
        findAns(a,t,cur,index+1,sum);
    }
    
    vector> combinationSum(vector& a, int t) 
    {
        vector temp;
        findAns(a,t,temp,0,0);
        return ans;
    }
};

class Solution {
public:
    
    vector> ans;
    map,int> mp;
    
    void findAns(vector &a,int t,vector &cur,int index,int sum)
    {
        if(sum==t)
        {
            sort(cur.begin(),cur.end());
            if(!mp[cur])
                ans.push_back(cur);
            mp[cur]++;
            return;
        }
            
        if(index>=a.size())
            return;
        
        
        if(sum+a[index]<=t)
        {
            vector temp=cur;
            temp.push_back(a[index]);
            findAns(a,t,temp,index+1,sum+a[index]);
            findAns(a,t,temp,index,sum+a[index]);
        }
        
        findAns(a,t,cur,index+1,sum);
    }
    
    vector> combinationSum(vector& a, int t) 
    {
        vector temp;
        findAns(a,t,temp,0,0);
        return ans;
    }
};

class Solution {
public:
    
    vector> ans;
    map,int> mp;
    
    void findAns(vector &a,int t,vector &cur,int index,int sum)
    {
        // cout<=a.size())
            return;
        
        
        if(sum+a[index]<=t)
        {
            // cout< temp=cur;
            temp.push_back(a[index]);
            findAns(a,t,temp,index+1,sum+a[index]);
            findAns(a,t,temp,index,sum+a[index]);
        }
        
        findAns(a,t,cur,index+1,sum);
    }
    
    vector> combinationSum(vector& a, int t) {
        ans.clear();
        vector temp;
        findAns(a,t,temp,0,0);
        return ans;
    }
};

class Solution {
public:
    
    vector> ans;
    map,int> mp;
    
    void findAns(vector &a,int t,vector &cur,int index,int sum)
    {
        // cout<=a.size())
            return;
        
        
        if(sum+a[index]<=t)
        {
            // cout< temp=cur;
            temp.push_back(a[index]);
            findAns(a,t,temp,index+1,sum+a[index]);
            findAns(a,t,temp,index,sum+a[index]);
        }
        
        findAns(a,t,cur,index+1,sum);
    }
    
    vector> combinationSum(vector& a, int t) {
        ans.clear();
        vector temp;
        findAns(a,t,temp,0,0);
        return ans;
    }
};

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

class Solution {
public:
    
    vector> ans;

void solve(vector v, int target, vector temp, int src) {

	if(src>v.size() || target<0) return; 
	if(!target) {ans.push_back(temp); return;}

	for(int i=src; isrc && v[i]==v[i-1]) continue; //Ignore duplicates
		
		//Backtracking:
		temp.push_back(v[i]);
		solve(v, target-v[i], temp, i+1);
		temp.pop_back();   
	}

	return;
}

//Driver function
vector> combinationSum2(vector v, int target) {  
	int n=v.size(); if(!n) return ans;
	sort(v.begin(), v.end());
	vector temp;
	solve(v, target, temp, 0);

	return ans;
}
};

class Solution {
public:
    
    vector> ans;

void solve(vector v, int target, vector temp, int src) {

	if(src>v.size() || target<0) return; 
	if(!target) {ans.push_back(temp); return;}

	for(int i=src; isrc && v[i]==v[i-1]) continue; //Ignore duplicates
		
		//Backtracking:
		temp.push_back(v[i]);
		solve(v, target-v[i], temp, i+1);
		temp.pop_back();   
	}

	return;
}

//Driver function
vector> combinationSum2(vector v, int target) {  
	int n=v.size(); if(!n) return ans;
	sort(v.begin(), v.end());
	vector temp;
	solve(v, target, temp, 0);

	return ans;
}
};

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

class Solution {
public:
    bool isMatch(string s, string p) {
        
        int n=s.size();
        int m=p.size();
        int dp[n+1][m+1];
        
        dp[0][0]=1;
        
        for(int i=1;i
  

class Solution {
public:
    bool isMatch(string s, string p) {
        
        int n=s.size();
        int m=p.size();
        int dp[n+1][m+1];
        
        dp[0][0]=1;
        
        for(int i=1;i

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

class Solution {
public:
    
    vector> v;
    map,int> ans;
    
    void permute(vector a)
    {
        if(ans.find(a)==ans.end())
        {
            ans[a]=1;
            v.push_back(a);
        }
        else
            return;
        
        int i,j;
        for(i=0;i> permuteUnique(vector& nums) {
        
        ans.clear();
        v.clear();
        
        if(nums.size())
            permute(nums);
        
        return v;
    }
};

class Solution {
public:
    
    vector> v;
    map,int> ans;
    
    void permute(vector a)
    {
        if(ans.find(a)==ans.end())
        {
            ans[a]=1;
            v.push_back(a);
        }
        else
            return;
        
        int i,j;
        for(i=0;i> permuteUnique(vector& nums) {
        
        ans.clear();
        v.clear();
        
        if(nums.size())
            permute(nums);
        
        return v;
    }
};

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

class Solution {
public:
    void rotate(vector>& matrix) {
        int i,j;
        for(i=0;i
  

class Solution {
public:
    void rotate(vector>& matrix) {
        int i,j;
        for(i=0;i

class Solution {
public:
    void rotate(vector>& matrix) {
        int i,j;
        for(i=0;i
  

class Solution {
public:
    void rotate(vector>& matrix) {
        int i,j;
        for(i=0;i

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n is an integer.
• Either x is not zero or n > 0.
• -104 <= xn <= 104

class Solution {
public:
    double myPow(double x, int n) {
        double res=1;
        int f=0;
        if(n<0)
            f=1;
        while(n)
        {
            if(n%2)
                res*=x;
            x*=x;
            n/=2;
        }
        if(f)
            return 1/res;
        return res;
    }
};

class Solution {
public:
    double myPow(double x, int n) {
        double res=1;
        int f=0;
        if(n<0)
            f=1;
        while(n)
        {
            if(n%2)
                res*=x;
            x*=x;
            n/=2;
        }
        if(f)
            return 1/res;
        return res;
    }
};

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

• 1 <= n <= 9

class Solution {
public:
    map,int> ans;

    bool valid(int row,int col,int n) {
        return (row>=0 && col>=0 && row &board,int row,int col,int n) {
        // check in row and column
        for(int j=0;j &board,int row,int n) {
        if(row==n) {
            ans[board]=1;
            return;
        }
        
        for(int col=0;col> solveNQueens(int n) {
        ans.clear();
        
        string row="";
        vector board;
        
        for(int i=0;i> ansVec;
        for(auto it: ans)
            ansVec.push_back(it.first);
        return ansVec;
    }
};

class Solution {
public:
    map,int> ans;

    bool valid(int row,int col,int n) {
        return (row>=0 && col>=0 && row &board,int row,int col,int n) {
        // check in row and column
        for(int j=0;j &board,int row,int n) {
        if(row==n) {
            ans[board]=1;
            return;
        }
        
        for(int col=0;col> solveNQueens(int n) {
        ans.clear();
        
        string row="";
        vector board;
        
        for(int i=0;i> ansVec;
        for(auto it: ans)
            ansVec.push_back(it.first);
        return ansVec;
    }
};

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 9

class Solution {
public:
    map,int> ans;

bool valid(int row,int col,int n) {
        return (row>=0 && col>=0 && row &board,int row,int col,int n) {
        // check in row and column
        for(int j=0;j board,int row,int n) {
        if(row==n) {
            ans[board]=1;
            return;
        }

        for(int col=0;col board(n,string(n,'.'));

        findAns(board,0,n);

        return ans.size();
    }
};

class Solution {
public:
    map,int> ans;

bool valid(int row,int col,int n) {
        return (row>=0 && col>=0 && row &board,int row,int col,int n) {
        // check in row and column
        for(int j=0;j board,int row,int n) {
        if(row==n) {
            ans[board]=1;
            return;
        }

        for(int col=0;col board(n,string(n,'.'));

        findAns(board,0,n);

        return ans.size();
    }
};

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {
public:
    int maxSubArray(vector& a) {
        int cur=0,mx=INT_MIN,i;
        for(i=0;i
  

class Solution {
public:
    int maxSubArray(vector& a) {
        int cur=0,mx=INT_MIN,i;
        for(i=0;i

class Solution {
public:
    int maxSubArray(vector& a) {
        int cur=0,mx=INT_MIN,i;
        for(i=0;i
  

class Solution {
public:
    int maxSubArray(vector& a) {
        int cur=0,mx=INT_MIN,i;
        for(i=0;i

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

class Solution {
public:
    bool canJump(vector& nums) {
        int i, end;
        end = nums.size() - 1;
        i = nums.size() - 2;
        
        while(i >= 0)
        {
            if(end - i <= nums[i]) // if we can reach end from the curr or not
            {
                end = i;
            }
            i--;
        }
        
        if(end==0) return true;
        else return false;
    }
};

class Solution {
public:
    bool canJump(vector& nums) {
        int i, end;
        end = nums.size() - 1;
        i = nums.size() - 2;
        
        while(i >= 0)
        {
            if(end - i <= nums[i]) // if we can reach end from the curr or not
            {
                end = i;
            }
            i--;
        }
        
        if(end==0) return true;
        else return false;
    }
};

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
       
        if(intervals.size()==0)
            return ans;
        
        sort(intervals.begin(),intervals.end());
        
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                ans.push_back({cur_min,cur_max});
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        ans.push_back({cur_min,cur_max});
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
       
        if(intervals.size()==0)
            return ans;
        
        sort(intervals.begin(),intervals.end());
        
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                ans.push_back({cur_min,cur_max});
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        ans.push_back({cur_min,cur_max});
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
       
        if(intervals.size()==0)
            return ans;
        
        sort(intervals.begin(),intervals.end());
        
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                ans.push_back({cur_min,cur_max});
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
       
        if(intervals.size()==0)
            return ans;
        
        sort(intervals.begin(),intervals.end());
        
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                ans.push_back({cur_min,cur_max});
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v) , v.clear();
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v) , v.clear();
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                v.push_back(cur_min);
                v.push_back(cur_max);
                ans.push_back(v);
                v.clear();
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                v.push_back(cur_min);
                v.push_back(cur_max);
                ans.push_back(v);
                v.clear();
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v) , v.clear();
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v) , v.clear();
                cur_min=intervals[i][0];
                if(intervals[i][1]>cur_max)
                    cur_max=intervals[i][1];
            }    
        }
        v.push_back(cur_min) , v.push_back(cur_max) , ans.push_back(v);
        return ans;
    }
};

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                // cout<cur_max)
                    cur_max=intervals[i][1];
            }    
            cout<
  

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector> ans;
        vector v;
        if(intervals.size()==0)
            return ans;
        sort(intervals.begin(),intervals.end());
        int cur_max=intervals[0][1],cur_min=intervals[0][0],i;
        for(i=1;icur_max)
                    cur_max=intervals[i][1];
            }
            else
            {
                // cout<cur_max)
                    cur_max=intervals[i][1];
            }    
            cout<

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

Constraints:

• 1 <= s.length <= 104
• s consists of only English letters and spaces ' '.
• There will be at least one word in s.

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:

Input: n = 1
Output: [[1]]

Constraints:

• 1 <= n <= 20

class Solution {
public:
    vector> generateMatrix(int n) {
        vector> a(n,vector(n,0));
        int i,j,cur=1;
        for(i=0;ii;j--)
                a[n-1-i][j]=cur++;
            for(j=(n-1-i);j>i;j--)
                a[j][i]=cur++;
        }
        if(n%2)
            a[n/2][n/2]=n*n;
        return a;
    }
};

class Solution {
public:
    vector> generateMatrix(int n) {
        vector> a(n,vector(n,0));
        int i,j,cur=1;
        for(i=0;ii;j--)
                a[n-1-i][j]=cur++;
            for(j=(n-1-i);j>i;j--)
                a[j][i]=cur++;
        }
        if(n%2)
            a[n/2][n/2]=n*n;
        return a;
    }
};

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Example 3:

Input: n = 3, k = 1
Output: "123"

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        
        int len=1;
        ListNode* p=head;
        while(p->next!=NULL)
        {
            len++;
            p=p->next;
        }
        
        p->next=head;
        
        k=k%len;
        int temp=len-k;
        
        while(temp--)
            p=p->next;
        
        head=p->next;
        p->next=NULL;
        
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        
        int len=1;
        ListNode* p=head;
        while(p->next!=NULL)
        {
            len++;
            p=p->next;
        }
        
        p->next=head;
        
        k=k%len;
        int temp=len-k;
        
        while(temp--)
            p=p->next;
        
        head=p->next;
        p->next=NULL;
        
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        
        int len=1;
        ListNode* p=head;
        while(p->next!=NULL)
        {
            len++;
            p=p->next;
        }
        
        p->next=head;
        
        k=k%len;
        int temp=len-k-1;
        p=head;
        
        while(temp--)
            p=p->next;
        
        head=p->next;
        p->next=NULL;
        
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        
        int len=1;
        ListNode* p=head;
        while(p->next!=NULL)
        {
            len++;
            p=p->next;
        }
        
        p->next=head;
        
        k=k%len;
        int temp=len-k-1;
        p=head;
        
        while(temp--)
            p=p->next;
        
        head=p->next;
        p->next=NULL;
        
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        int len=0;
        ListNode* p=head;
        while(p!=NULL)
        {
            len++;
            p=p->next;
        }
        p=head;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        p->next=head;
        
        k=k%len;
        int temp=len-k-1;
        p=head;
        cout<next;
        }
        head=p->next;
        p->next=NULL;
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL)
            return NULL;
        int len=0;
        ListNode* p=head;
        while(p!=NULL)
        {
            len++;
            p=p->next;
        }
        p=head;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        p->next=head;
        
        k=k%len;
        int temp=len-k-1;
        p=head;
        cout<next;
        }
        head=p->next;
        p->next=NULL;
        return head;
    }
};

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

• 1 <= m, n <= 100

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long int N=n+m-2;
        long long int r=n-1;
        long long int ans=1;
        for(int i=1;i<=r;i++)
            ans=ans*(N-r+i)/i;
        return (int)ans;
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long int N=n+m-2;
        long long int r=n-1;
        long long int ans=1;
        for(int i=1;i<=r;i++)
            ans=ans*(N-r+i)/i;
        return (int)ans;
    }
};

class Solution {
public:
    
    int dp[101][101];
    int findPaths(int x,int y,int m,int n)
    {
        if(x==m-1 && y==n-1)
            return 1;
        if(x>=m || y>=n)
            return 0;
        if(dp[x][y]!=-1)
            return dp[x][y];
        else
        {
            dp[x][y]=findPaths(x+1,y,m,n) + findPaths(x,y+1,m,n);
            return dp[x][y];
        }   
    }
    
    int uniquePaths(int m, int n) {
        memset(dp,-1,sizeof(dp));
        return findPaths(0,0,m,n);
    }
};

class Solution {
public:
    
    int dp[101][101];
    int findPaths(int x,int y,int m,int n)
    {
        if(x==m-1 && y==n-1)
            return 1;
        if(x>=m || y>=n)
            return 0;
        if(dp[x][y]!=-1)
            return dp[x][y];
        else
        {
            dp[x][y]=findPaths(x+1,y,m,n) + findPaths(x,y+1,m,n);
            return dp[x][y];
        }   
    }
    
    int uniquePaths(int m, int n) {
        memset(dp,-1,sizeof(dp));
        return findPaths(0,0,m,n);
    }
};

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

class Solution {
public:
    int minPathSum(vector>& a) {
        int i,j,n=a.size(),m=a[0].size();
        
        for(i=1;i
  

class Solution {
public:
    int minPathSum(vector>& a) {
        int i,j,n=a.size(),m=a[0].size();
        
        for(i=1;i

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0's.

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Note:

• A word is defined as a character sequence consisting of non-space characters only.
• Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
• The input array words contains at least one word.

Example 1:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Example 2:

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Explanation: Note that the last line is "shall be    " instead of "shall     be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.

Example 3:

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

Constraints:

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] consists of only English letters and symbols.
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

• 0 <= x <= 231 - 1

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

• 1 <= n <= 45

class Solution {
public:
    int climbStairs(int n) {
        int dp[46]={0},i;
        dp[1]=1,dp[2]=2;
        for(i=3;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n];
    }
};

class Solution {
public:
    int climbStairs(int n) {
        int dp[46]={0},i;
        dp[1]=1,dp[2]=2;
        for(i=3;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n];
    }
};

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

• The path starts with a single slash '/'.
• Any two directories are separated by a single slash '/'.
• The path does not end with a trailing '/'.
• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Constraints:

• 1 <= path.length <= 3000
• path consists of English letters, digits, period '.', slash '/' or '_'.
• path is a valid absolute Unix path.

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

class Solution {
public:
    int dp[501][501];
    int solve(string word1,string word2,int n,int m)
    {
        if(n == 0)
            return m ;
     
        if(m == 0)
            return n;
        
        if(m == 0 && n ==0 )
            return 0;
    
        if(dp[n][m] != -1)
            return dp[n][m];
        
        if(word1[n-1] == word2[m-1])
            return solve(word1,word2,n-1,m-1);
        
    
        int ans = 1 + min(solve(word1,word2,n,m-1) ,min(solve(word1,word2,n-1,m),
                         solve(word1,word2,n-1,m-1)));
        return dp[n][m] = ans;
    }
    
    int minDistance(string word1, string word2) 
    {
        int  n =word1.size();
        int m = word2.size();
        memset(dp , -1,sizeof(dp));
        return solve(word1,word2,n,m);
    }
};

class Solution {
public:
    int dp[501][501];
    int solve(string word1,string word2,int n,int m)
    {
        if(n == 0)
            return m ;
     
        if(m == 0)
            return n;
        
        if(m == 0 && n ==0 )
            return 0;
    
        if(dp[n][m] != -1)
            return dp[n][m];
        
        if(word1[n-1] == word2[m-1])
            return solve(word1,word2,n-1,m-1);
        
    
        int ans = 1 + min(solve(word1,word2,n,m-1) ,min(solve(word1,word2,n-1,m),
                         solve(word1,word2,n-1,m-1)));
        return dp[n][m] = ans;
    }
    
    int minDistance(string word1, string word2) 
    {
        int  n =word1.size();
        int m = word2.size();
        memset(dp , -1,sizeof(dp));
        return solve(word1,word2,n,m);
    }
};

class Solution {
public:
    int minDistance(string s, string s1) {
        
        int dp[505][505],i,j,n=s.length(),m=s1.length();
        
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=m;j++)
            {
                if(i==0)
                    dp[i][j]=j;
                else if(j==0)
                    dp[i][j]=i;
                else if(s[i-1]==s1[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=1+min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]));
            }
        }   
        
        return dp[n][m];
    }
};

class Solution {
public:
    int minDistance(string s, string s1) {
        
        int dp[505][505],i,j,n=s.length(),m=s1.length();
        
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=m;j++)
            {
                if(i==0)
                    dp[i][j]=j;
                else if(j==0)
                    dp[i][j]=i;
                else if(s[i-1]==s1[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=1+min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]));
            }
        }   
        
        return dp[n][m];
    }
};

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

Follow up:

• A straightforward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

class Solution {
public:
    void setZeroes(vector>& a) {
        
        int i,j,n=a.size(),m=a[0].size(),col=0;
        for(i=0;i
  

class Solution {
public:
    void setZeroes(vector>& a) {
        
        int i,j,n=a.size(),m=a[0].size(),col=0;
        for(i=0;i

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

class Solution {
public:
    void sortColors(vector& nums) {
        int a[3]={0},i;
        for(auto el : nums)
            a[el]++;
        int j=0;
        for(i=0;i
  

class Solution {
public:
    void sortColors(vector& nums) {
        int a[3]={0},i;
        for(auto el : nums)
            a[el]++;
        int j=0;
        for(i=0;i

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

class Solution {
public:
    vector> subsets(vector& nums) {
        vector> v;
        int tot=1< a;
            for(j=0;j
  

class Solution {
public:
    vector> subsets(vector& nums) {
        vector> v;
        int tot=1< a;
            for(j=0;j

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

class Solution {
public:
    int largestRectangleArea(vector& h) {
        h.push_back(0);
        
        int i,ans=0;
        
        stack indices;
        
        for(i=0;i
  

class Solution {
public:
    int largestRectangleArea(vector& h) {
        h.push_back(0);
        
        int i,ans=0;
        
        stack indices;
        
        for(i=0;i